home *** CD-ROM | disk | FTP | other *** search
/ Oh!X 2001 Spring / Oh!X 2001 Spring Special CD-ROM (Japan).7z / Oh!X 2001 Spring Special CD-ROM (Japan) (Track 1).bin / PUZZLE / puz01 / ms1.c < prev    next >
C/C++ Source or Header  |  2000-02-20  |  2KB  |  105 lines
  1. /*
  2.  * ms1.c : マジックスター全解探索
  3.  *
  4.  *               Copyright (C) 2000 by Makoto Hiroi
  5.  *
  6.  */
  7. /*
  8.         パズルの内容
  9.  
  10.                 ０
  11.               ／  ＼
  12.     １------２------３------４
  13.       ＼  ／          ＼  ／             
  14.         ５              ６
  15.       ／  ＼          ／  ＼
  16.     ７------８------９------10
  17.               ＼  ／  
  18.                 11
  19.  
  20.     1 - 12 の数字を入れて直線上にある４つの数字の和が
  21.     全て 26 になるようにする
  22.  
  23.     直線
  24.     0-2-5-7, 0-3-6-10, 7-8-9-10
  25.     1-2-3-4, 1-5-8-11, 4-6-9-11
  26. */
  27.  
  28. #include <stdio.h>
  29. #include <stdlib.h>
  30. #include <string.h>
  31. #include <time.h>
  32.  
  33. #define TRUE  1
  34. #define FALSE 0
  35. #define N     12
  36. #define LINE  6
  37.  
  38. const char line[LINE][4] = {
  39.   0, 2, 5, 7,  0, 3, 6, 10,  7, 8, 9, 10,
  40.   1, 2, 3, 4,  1, 5, 8, 11,  4, 6, 9, 11
  41. };
  42.  
  43. char star[N];
  44. char use_number[N + 1];
  45. int  count = 0;
  46.  
  47. /* 出力 */
  48. void print_star( void )
  49. {
  50.   int i;
  51.   for( i = 0; i < N; i++ ){
  52.     printf("%2d ", star[i] );
  53.   }
  54.   printf("\n");
  55. }
  56.  
  57. /* 星の検査 */
  58. int check_star( void )
  59. {
  60.   int i;
  61.   for( i = 0; i < LINE; i++ ){
  62.     int j, n;
  63.     for( j = n = 0; j < 4; j++ ){
  64.       n += star[ line[i][j] ];
  65.     }
  66.     if( n != 26 ) return FALSE;
  67.   }
  68.   return TRUE;
  69. }
  70.  
  71. /* 単純な生成検定法 */
  72. void search_star( int n )
  73. {
  74.   int i;
  75.   if( n == N && check_star() ){
  76.     count++;
  77.     print_star();
  78.   } else {
  79.     for( i = 1; i <= N; i++ ){
  80.       if( !use_number[i] ){
  81.     use_number[i] = TRUE;
  82.     star[n] = i;
  83.     search_star( n + 1 );
  84.         use_number[i] = FALSE;
  85.       }
  86.     }
  87.   }
  88. }
  89.  
  90. int main()
  91. {
  92.   int start, end;
  93.   memset( use_number, 0, N + 1 );   /* 初期化 */
  94.   printf("時間がかかるので１から始まる順列のみをチェックする\n");
  95.   use_number[1] = TRUE;
  96.   star[0] = 1;
  97.   start = clock();
  98.   search_star( 1 );
  99.   end = clock();
  100.   printf("総数 %d 個, 時間 %d\n", count, end - start );
  101.   return 0;
  102. }
  103.  
  104. /* end of file */
  105.